package secondary

/*
	输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

	B是A的子结构， 即 A中有出现和B相同的结构和节点值。

	返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

	示例 1：

	输入：A = [1,2,3], B = [3,1]
	输出：false
	示例 2：

	输入：A = [3,4,5,1,2], B = [4,1]
	输出：true
	限制：

	0 <= 节点个数 <= 10000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func isSubStructure(A *TreeNode, B *TreeNode) bool {
	if nil == A || nil == B {
		return false
	}
	// 1. 找到A树中与B树根节点相同的节点R
	// 2. 判断以R为根节点的子树与B是否有相同的结构
	return recurseSameStruct(A, B) || isSubStructure(A.Left, B) || isSubStructure(A.Right, B)
}

func recurseSameStruct(a *TreeNode, b *TreeNode) bool {
	if nil == b {
		return true
	}
	if nil == a {
		return false
	}

	if a.Val != b.Val {
		return false
	}
	return recurseSameStruct(a.Left, b.Left) && recurseSameStruct(a.Right, b.Right)
}
